from itertools import combinations

def knapsack_brute_force(W, weights, values, N):
    max_value = 0
    best_combination = []
    
    # 遍历所有可能的物品组合（选 0~N 个物品）
    for k in range(1, N + 1):
        for indices in combinations(range(N), k):  # 选 k 个物品的所有组合
            total_weight = sum(weights[i] for i in indices)
            total_value = sum(values[i] for i in indices)
            if total_weight <= W and total_value > max_value:
                max_value = total_value
                best_combination = indices
    return max_value, best_combination

# 示例
W = 10
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
N = len(weights)
max_val, items = knapsack_brute_force(W, weights, values, N)
print("最大价值:", max_val)  # 10
print("选择的物品索引:", items)  # (1, 3) 或 (3, 1)